/* 最小割应用
    由于是异或和，可以每一位单独考虑，对于第k位而言，可以分为0和1两个集合，
    即建立源点 s，第k位为1的点放在 s 这边形成最小割的 S 部分，s向这部分点连边，容量足够大，建立汇点 t，
    第 k 位为 0 的点放在 t 这边形成最小割的 T 部分，这部分点向 t 连边，容量也足够大，已知标号的点显然可以建立 s 和 t 的关系，
    对于未知标号的点，考虑流网络直接在原图上建边，即对于原图上的任意一条边 (x,y)，直接在流网络上建立从 x 到 y 以及 y 到 x 的边，容量为 1
    最后求解最小割 x 即为第 k 的贡献，即对于第 k 位来说至少有 x 条边该位为 1，即该位答案至少为 m×2k

    显然求的是最小割，即割上不应该出现容量足够大的边，即一开始所有已知标号的点的第 k 位就已经分好了位置，即对于已知第 k 位为 1 的点分在最小割的 S 部分，
    对于第 k 位为 0 的点分在最小割的 T 部分，要使这样的异或为 1 的边最少，
    因为对于 S 和 T 其内部形成的边的异或都为 0，所以只考虑两部分中间的边，要求这样的边越少越好，即 S 和 T 两部分之间的边的容量越少越好，
    即最小割（开始流网络在原图上建边时每条边的容量设为 1，最小割值为多少就说明有多少条边）

*/

#define DEBUG
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
#define int long long
using PII = pair<int, int>;
#define x first
#define y second
const int N = 510, M = (3000+N) *2, INF = 0x3f3f3f3f;
int n, m, k, S, T;
int e[M], h[N], c[M], ne[M], idx;
int q[N], cur[N], d[N];
int pa[N];
PII edges[3010];

void AddEdge(int a, int b, int c1, int c2)
{
    e[idx] = b, c[idx] = c1, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, c[idx] = c2, ne[idx] = h[b], h[b] = idx++;
}

bool bfs()
{
    int hh = 0, tt = -1;
    memset(d, -1, sizeof d);
    q[++tt] = S, cur[S] = h[S], d[S] = 0;
    while(hh <= tt)
    {
        int u = q[hh++];
        for(int i = h[u]; ~i; i = ne[i])
        {
            int v = e[i];
            if(d[v] == -1 && c[i])
            {
                d[v] = d[u] + 1;
                cur[v] = h[v];
                if(v == T) return true;
                q[++tt] = v;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && limit > flow; cur[u] = i, i = ne[i])
    {
        int v = e[i];
        if(d[v] == d[u] + 1 && c[i])
        {
            int t = find(v, min(c[i], limit - flow));
            if(!t) d[v] = -1;
            c[i] -= t, c[i^1] += t, flow += t;
        }
    }
    return flow;
}

void build(int k)
{
    memset(h, -1, sizeof h);
    idx = 0;
    for(int i = 0;  i< m; i++)
    {
        int a = edges[i].x, b = edges[i].y;
        AddEdge(a, b, 1, 1);
    }

    for(int i = 1; i <= n; i++)
        if(pa[i] >= 0)
            if(pa[i] >> k & 1) AddEdge(i, T, INF, 0);
            else AddEdge(S, i, INF, 0);
}

int Dinic(int k) //枚举第k位
{
    int res = 0, flow = 0;
    build(k);
    while(bfs())
        while((flow = find(S, INF))) res += flow;
    return res; 
}

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt", "r", stdin);
    #else
        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    cin >> n >> m;
    S = 0, T = n+1;
    for(int i=0; i<m; i++)
    {
        cin >> edges[i].x >> edges[i].y;
    }

    cin >> k;
    memset(pa, -1, sizeof pa);
    while(k--)
    {
        int a, b; cin >> a >> b; //a的标号是b
        pa[a] = b;
    }

    int res = 0;
    for(int i = 0; i <= 30; i++) res += Dinic(i) << i; //枚举每一位
    printf("%lld\n", res);
    return 0;
}
